BIT Algo/2. Zajęcia/Zadanie 8. (Sortowanie listy odsyłaczowej o wartościach o rozkładzie jednostajnym).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dana jest klasa:\n",
    "\n",
    "    class Node:\n",
    "        self.val = 0\n",
    "        self.next = None\n",
    "        \n",
    "> Klasa reprezentuje węzeł jednokierunkowego łańcucha odsyłaczowego, w którym wartości $ val $ poszczególnych węzłów zostały wygenerowane zgodnie z rozkładem jednostajnym na przedziale $ [a, b] $. \n",
    "\n",
    "> Napisz procedurę $ sort(first) $, która sortuje taką listę. Funkcja powinna być możliwie najszybsza."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ mamy powiedziane, że wartości zostały wygenerowane zgodnie z rozkładem jednostajnym, od razu na myśl przychodzi Bucket Sort. Jest to jedyny liniowy algorytm sortowania list odsyłaczowych, który pozwala na ich łatwe posortowanie i się idealnie do tego celu nadaje."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Implementacja klasy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "        \n",
    "\n",
    "def create_linked_list(values: 'iterable' = None) -> 'linked list head (sentinel)':\n",
    "    head = Node()  # A sentinel node\n",
    "    if not values: return head\n",
    "    head.next = curr = Node(values[0])\n",
    "    for i in range(1, len(values)):\n",
    "        curr.next = Node(values[i])\n",
    "        curr = curr.next\n",
    "    return head\n",
    "\n",
    "\n",
    "def linked_list_to_list(ll_head: 'linked list head (sentinel)') -> list:\n",
    "    values = []\n",
    "    curr = ll_head.next\n",
    "    while curr:\n",
    "        values.append(curr.val)\n",
    "        curr = curr.next\n",
    "    return values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Implementacja funkcji sortującej"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bucket_sort(ll_head: 'linked list head (sentinel)', min_val, max_val):\n",
    "    length = linked_list_length(ll_head)\n",
    "    if length < 65:\n",
    "        insertion_sort(ll_head)\n",
    "    else:\n",
    "        k = 48\n",
    "        buckets_count = length // k + 1\n",
    "        # Create buckets (a list of sentinel nodes)\n",
    "        buckets = []\n",
    "        for _ in range(buckets_count):\n",
    "            sentinel = tail = Node()\n",
    "            buckets.append([sentinel, tail])\n",
    "        # Calculate an interval in order to store values in proper buckets\n",
    "        val_interval = (max_val - min_val) / buckets_count\n",
    "        # Distribute values to the proper buckets\n",
    "        curr = ll_head.next\n",
    "        while curr:\n",
    "            # Calculate the bucket's index depending on how much the \n",
    "            # current value is greater than the lowest one\n",
    "            bucket_idx = int((curr.val - min_val) / val_interval - .5)\n",
    "            buckets[bucket_idx][1].next = curr\n",
    "            buckets[bucket_idx][1] = curr\n",
    "            curr = curr.next\n",
    "        # Sort each bucket separately\n",
    "        for bucket in buckets:\n",
    "            # Remove tail's next node and update a tail after sorting\n",
    "            bucket[1].next = None\n",
    "            bucket[1] = insertion_sort(bucket[0])\n",
    "        # Link buckets together to create a sorted list\n",
    "        sorted_tail = ll_head\n",
    "        for bucket in buckets:\n",
    "            # If a bucket is not empty, link a list to he result\n",
    "            if bucket[0].next:\n",
    "                sorted_tail.next = bucket[0].next\n",
    "                sorted_tail = bucket[1]\n",
    "            \n",
    "            \n",
    "def linked_list_length(ll_head: 'linked list head (sentinel)'):\n",
    "    curr = ll_head.next\n",
    "    length = 0\n",
    "    while curr:\n",
    "        length += 1\n",
    "        curr = curr.next\n",
    "    return length\n",
    "\n",
    "\n",
    "# Inserts node in a right position maintaining the ascending order\n",
    "def insert_node(ll_head: 'linked list head (sentinel)', node):\n",
    "    # Insert the node before a greater one\n",
    "    curr = ll_head\n",
    "    while node.val > curr.next.val:\n",
    "        curr = curr.next\n",
    "    node.next = curr.next\n",
    "    curr.next = node\n",
    "        \n",
    "    \n",
    "def insertion_sort(ll_head: 'linked list head (sentinel)'):\n",
    "    if not ll_head.next or not ll_head.next.next: return ll_head\n",
    "    \n",
    "    prev = ll_head.next\n",
    "    while prev.next: # We start from the second node (prev.next)\n",
    "        # If a current node (prev.next) has a value lower than a prev \n",
    "        # node, we have to shift this node to a right position before.\n",
    "        if prev.next.val < prev.val:\n",
    "            # Remove a current node\n",
    "            removed = prev.next\n",
    "            prev.next = prev.next.next\n",
    "            # Now we insert this node in a right position\n",
    "            insert_node(ll_head, removed)\n",
    "        # We can skip a current node otherwise.\n",
    "        else:\n",
    "            prev = prev.next \n",
    "    \n",
    "    return prev"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input: [51, -36, 17, -84, 38, -18, 58, -43, 1, 66, -21, 5, 74, -11, 60, 87, -22, 26, 10, 35, -33, -93, -50, 91, 89, -71, -17, -65, 26, -92, -44, 28, 69, 27, 20, -44, -30, 33, 0, 23, 27, -64, -21, -90, -59, -4, 62, -34, 97, 34, -7, -92, -11, 71, -6, -7, 62, 61, 1, 0, 10, -96, -14, 33, 75, -64, 27, 8, 19, 46, -9, -74, 97, -90, 83, 13, -29, 0, -80, 72, -75, -7, -26, 29, -90, -74, 99, 79, 71, 100, -15, -83, -21, 56, -47, -12, -22, 81, -29, -89, -97, -51, 8, 50, -40, -27, -17, 33, 59, 1, 43, 42, -86, -16, 36, -99, -30, 63, 100, 29, 51, 13, -71, 42, 86, 67, -19, -37, 35, -56, 56, -15, -40, -1, 51, -94, 16, -82, -80, 27, -59, -97, -89, -67, 38, 35, -58, 4, -42, 30, -75, 54, -85, -86, 57]\n",
      "\n",
      "Result: [-99, -97, -97, -96, -94, -93, -92, -92, -90, -90, -90, -89, -89, -86, -86, -85, -84, -83, -82, -80, -80, -75, -75, -74, -74, -71, -71, -67, -65, -64, -64, -59, -59, -58, -56, -51, -50, -47, -44, -44, -43, -42, -40, -40, -37, -36, -34, -33, -30, -30, -29, -29, -27, -26, -22, -22, -21, -21, -21, -19, -18, -17, -17, -16, -15, -15, -14, -12, -11, -11, -9, -7, -7, -7, -6, -4, -1, 0, 0, 0, 1, 1, 1, 4, 5, 8, 8, 10, 10, 13, 13, 16, 17, 19, 20, 23, 26, 26, 27, 27, 27, 27, 28, 29, 29, 30, 33, 33, 33, 34, 35, 35, 35, 36, 38, 38, 42, 42, 43, 46, 50, 51, 51, 51, 54, 56, 56, 57, 58, 59, 60, 61, 62, 62, 63, 66, 67, 69, 71, 71, 72, 74, 75, 79, 81, 83, 86, 87, 89, 91, 97, 97, 99, 100, 100]\n",
      "\n",
      "Expected: [-99, -97, -97, -96, -94, -93, -92, -92, -90, -90, -90, -89, -89, -86, -86, -85, -84, -83, -82, -80, -80, -75, -75, -74, -74, -71, -71, -67, -65, -64, -64, -59, -59, -58, -56, -51, -50, -47, -44, -44, -43, -42, -40, -40, -37, -36, -34, -33, -30, -30, -29, -29, -27, -26, -22, -22, -21, -21, -21, -19, -18, -17, -17, -16, -15, -15, -14, -12, -11, -11, -9, -7, -7, -7, -6, -4, -1, 0, 0, 0, 1, 1, 1, 4, 5, 8, 8, 10, 10, 13, 13, 16, 17, 19, 20, 23, 26, 26, 27, 27, 27, 27, 28, 29, 29, 30, 33, 33, 33, 34, 35, 35, 35, 36, 38, 38, 42, 42, 43, 46, 50, 51, 51, 51, 54, 56, 56, 57, 58, 59, 60, 61, 62, 62, 63, 66, 67, 69, 71, 71, 72, 74, 75, 79, 81, 83, 86, 87, 89, 91, 97, 97, 99, 100, 100]\n",
      "\n",
      "An algorithm is CORRECT\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "a, b = -100, 100\n",
    "random_lst = [random.randint(a, b) for _ in range(random.randint(50, 250))]\n",
    "expected = sorted(random_lst)\n",
    "print('Input:', random_lst)\n",
    "ll_head = create_linked_list(random_lst)\n",
    "bucket_sort(ll_head, a, b)\n",
    "result_lst = linked_list_to_list(ll_head)\n",
    "print('\\nResult:', result_lst)\n",
    "print('\\nExpected:', expected)\n",
    "print(f'\\nAn algorithm is {\"CORRECT\" if expected == result_lst else \"WRONG\"}')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}